package com.interview.sorting;

/**
 * 插入排序
 * 算法：经过i-1遍处理后，L[1..i-1]己排好序。
 * 第i遍处理仅将L[i]插入L[1..i-1]的适当位置，
 * 使得L[1..i]又是排好序的序列。
 * 要达到这个目的，我们可以用顺序比较的方法。
 * 首先比较L[i]和L[i-1]，如果L[i-1]<=L[i]，
 * 则L[1..i]已排好序，第i遍处理就结束了;
 * 否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，
 * 直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
 * 优点:移动元素次数少，只需要一个辅助空间
 */

public class InsertSort {
	public static void main(String[] args) {
		int[] values = { 5, 2, 4, 1, 3 };
		sort(values);
		for (int i = 0; i < values.length; i++) {
			System.out.print(values[i] + ",");
		}
	}

	// 直接插入排序
	public static void sort(int[] values) {
		int temp;
		int j = 0;
		for (int i = 1; i < values.length; i++) {
			if (values[i] < values[i - 1])// 这里体现了插入排序比冒泡排序和选择排序快的原因。
			{
				temp = values[i];
				// 数据往后移动
				for (j = i - 1; j >= 0 && temp < values[j]; j--) {
					values[j + 1] = values[j];
				}
				values[j + 1] = temp;// 将数据插入到j+1位置
				
//				System.out.print("第" + (i + 1) + "次：");
//				for (int k = 0; k < values.length; k++) {
//					System.out.print(values[k] + ",");
//				}
//				System.out.println("");
			}
		}
	}
}